public class Solution {
    //超时
    public static int InversePairs1(int [] a) {
        int result=0;
        int[] b = new int[a.length];//default 0
        for(int i=0; i< a.length; i++){
            for(int j=i-1;j>=0;j--){
                if(a[j]>a[i])
                    b[i]++;
            }
        }
        for(int i=0; i<b.length;i++){
            result = (result+b[i])%1000000007;
        }
        return result;
    }
    //归并排序的思想o（nlogn）
    //求中点，两个子问题，merge。边merge边数数
    static int count=0;
    public static int InversePairs(int [] a) {
        int[] copy = new int[a.length];
        for(int i=0; i<a.length; i++){
            copy[i] = a[i];
        }
        MergeSort(copy,0,copy.length-1);
        return count;
    }
    public static void MergeSort(int[] a,int start, int end){
        if(start>=end)
            return;
        int mid = (start+end)/2;
        MergeSort(a,start,mid);
        MergeSort(a,mid+1,end);
        merge(a,start,mid,mid+1,end);
    }
    
    public static void merge(int[] array, int start, int mid, int mid1, int end){
        int startc=start;
        int endc = end;
        int midc = mid;
//        int mid1c = mid1;
        while(true){
            while(mid>=start && array[mid]>array[end]){
                    count+=end-mid1+1;
                    count%=1000000007;
                    mid--;
            }
            while(mid>=0 && end>=mid1 && array[mid]<=array[end]){
                    end--;
            }
            if(mid<start || end<mid1)
                break;
        }
        start = startc;
        mid = midc;
        end = endc;
        int[] temp = new int[end-start+1];
        int i=0;
        //1:内部逆序个数,排序
        //2:指针指向最后，p1>p2 +length，p1前移，p1<p2,p2前移
        while(start<=mid && mid1<=end){
            temp[i++] = array[start]<array[mid1]?array[start++]:array[mid1++];
        }
        while(start<=mid){
            temp[i++] = array[start++];
        }
        while(mid1<=end){
            temp[i++] = array[mid1++];
        }
        i = 0;
        for(int j=startc; j<=end; j++){
            array[j] = temp[i++];
        }
    }

    public static void main(String args[]){
        int[] a =new int[]{364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
        int b = InversePairs(a);
        System.out.println(b);
    }

}

